<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      class Node {
        constructor(val) {
          this.val = val;
          this.left = null;
          this.right = null;
        }
      }
      class BinaryTree {
        constructor() {
          this.root = null;
        }
        insert(val) {
          const newNode = new Node(val);
          if (this.root === null) {
            this.root = newNode;
          } else {
            this.insertNode(newNode, this.root);
          }
        }
        insertNode(newNode, root) {
          if (newNode.val < root.val) {
            if (root.left === null) {
              root.left = newNode;
            } else {
              this.insertNode(newNode, root.left);
            }
          } else {
            if (root.right === null) {
              root.right = newNode;
            } else {
              this.insertNode(newNode, root.right);
            }
          }
        }
        preOrder(root = this.root) {
          if (root) {
            console.log(root.val);
            this.preOrder(root.left);
            this.preOrder(root.right);
          }
        }
        // 迭代法 中左右->右左中
        preOrder2(root = this.root) {
          let stack = [],
            res = [];
          if (!root) return res;
          stack.push(root);
          while (stack.length) {
            const node = stack.pop();
            if (!node) {
              res.push(stack.pop().val);
              continue;
            }
            if (node.right) stack.push(node.right);
            if (node.left) stack.push(node.left);
            stack.push(node);
            stack.push(null);
          }
          console.log(res);
        }
      }

      let tree = new BinaryTree();
      tree.insert(3);
      tree.insert(1);
      tree.insert(2);
      tree.insert(4);
      tree.insert(0);
      tree.insert(9);
      tree.insert(6);
      tree.preOrder();
      tree.preOrder2();
    </script>
  </body>
</html>
